package com.mlamp.排序算法;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class 桶排序 {
    public static void main(String[] args) {
        int[] ints = 基础排序.generateArray(30);
        List<Integer> integers = bucketSort(Arrays.stream(ints).boxed().collect(Collectors.toList()), 2);
        System.out.println(Arrays.toString(integers.toArray()));
    }

    public static List<Integer> bucketSort(List<Integer> array, int bucketSize) {
        if (array == null || array.size() < 2) return array;
        int max = array.get(0), min = array.get(0);
        for (int i = 0; i < array.size(); i++) {
            if (array.get(i) > max) {
                max = array.get(i);
            }
            if (array.get(i) < min) {
                min = array.get(i);
            }
        }
        int bucketCount = (max - min) / bucketSize + 1;
        List<ArrayList<Integer>> buckets = new ArrayList<>(bucketCount);
        List<Integer> results = new ArrayList<>();
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(i, new ArrayList<>());
        }
        for (int i = 0; i < array.size(); i++) {
            int bucketIndex = (array.get(i) - min) / bucketSize;
            buckets.get(bucketIndex).add(array.get(i));
        }
        for (int i = 0; i < bucketCount; i++) {
            if (bucketSize == 1) {
                for (int j = 0; j < buckets.get(i).size(); j++) {
                    results.add(buckets.get(i).get(j));
                }
            } else {
                if (bucketCount == 1) bucketSize--;
                List<Integer> integers = bucketSort(buckets.get(i), bucketSize);
                for (int j = 0; j < integers.size(); j++) {
                    results.add(integers.get(j));
                }
            }
        }
        return results;
    }
}
